package leetcode_101_120;

import utils.TreeNode;

public class sortedArrayToBST_108 {
    /**
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     * @param nums 升序 排列
     * @return 转换为一棵 高度平衡 二叉搜索树
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode node=new TreeNode();
        dfs(node,nums,0,nums.length-1,0);
        return node;
    }

    /**
     * 递归构造高度平衡二叉树
     * 0ms，easy
     * @param node 当前二叉树的根节点
     * @param nums 二叉搜索树的数组
     * @param left 数组左右边界
     * @param right
     * @param flag 判定左右子树，0左，1右
     */
    void dfs(TreeNode node,int[] nums,int left,int right,int flag){
        int mid=left + (right - left) / 2;
        if (right - left == 1 && flag==0 ) {  //如果只剩两个数字，并且是在处理左子树，上面的计算默认根节点偏左
            mid++; // 需要使根节点靠右，达到大于左子树的目的
        }
        node.val=nums[mid];

        if(left==right)
            return;

        if (mid != left) {
            node.left = new TreeNode();
            dfs(node.left, nums, left, mid - 1,0);
        }
        if (mid != right) {
            node.right = new TreeNode();
            dfs(node.right , nums, mid+1, right,1);
        }
    }
}
